{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Equal Count Substrings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #counting #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #计数 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: equalCountSubstrings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #等计数子串的数量"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始的字符串 <code>s</code>，只包含小写英文字母和一个整数 <code>count</code>。如果&nbsp;<code>s</code>&nbsp;的&nbsp;<strong>子串 </strong>中的每种字母在子串中恰好出现 <code>count</code> 次，这个子串就被称为&nbsp;<strong>等计数子串</strong>。</p>\n",
    "\n",
    "<p>返回<em> <code>s</code> 中&nbsp;<strong>等计数子串&nbsp;</strong>的个数。</em></p>\n",
    "\n",
    "<p><strong>子串&nbsp;</strong>是字符串中连续的非空字符序列。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> s = \"aaabcbbcc\", count = 3\n",
    "<strong>输出:</strong> 3\n",
    "<strong>解释:</strong>\n",
    "从下标 0 开始到下标 2 结束的子串是 \"aaa\"。\n",
    "字母 “a” 在子串中恰好出现了 3 次。\n",
    "从下标 3 开始到下标 8 结束的子串是 \"bcbbcc\"。\n",
    "字母 “b” 和 “c” 在子串中恰好出现了 3 次。\n",
    "从下标 0 开始到下标 8 结束的子串是 \"aaabcbbcc\"。\n",
    "字母 “a”、“b” 和 “c” 在子串中恰好出现了 3 次。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> s = \"abcd\", count = 2\n",
    "<strong>输出:</strong> 0\n",
    "<strong>解释:</strong>\n",
    "每种字母在 s 中出现的次数小于 count。\n",
    "因此，s 中没有子串是等计数子串，返回 0。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> s = \"a\", count = 5\n",
    "<strong>输出:</strong> 0\n",
    "<strong>解释:</strong>\n",
    "每种字母在 s 中出现的次数小于 count。\n",
    "因此，s 中没有子串是等计数子串，返回 0。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 3 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= count &lt;= 3 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>s</code> 只由小写英文字母组成。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-equal-count-substrings](https://leetcode.cn/problems/number-of-equal-count-substrings/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-equal-count-substrings](https://leetcode.cn/problems/number-of-equal-count-substrings/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"aaabcbbcc\"\\n3', '\"abcd\"\\n2', '\"a\"\\n5']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalCountSubstrings(self, s: str, c: int) -> int:  \n",
    "        ans = 0 \n",
    "        for j in range(1, 27):\n",
    "            a  = j*c \n",
    "            if len(s)<a:\n",
    "                pass \n",
    "            else:\n",
    "                b = defaultdict(int)\n",
    "                tmp = 0\n",
    "                for k in range(a):\n",
    "                    b[s[k]]+=1\n",
    "                    if b[s[k]]==c:\n",
    "                        tmp+=1 \n",
    "                    if b[s[k]]==(c+1):\n",
    "                        tmp-=1\n",
    "                if tmp==j:\n",
    "                    ans += 1 \n",
    "                for k in range(a, len(s)):\n",
    "                    b[s[k]]+=1\n",
    "                    if b[s[k]]==c:\n",
    "                        tmp+=1 \n",
    "                    if b[s[k]]==(c+1):\n",
    "                        tmp-=1 \n",
    "                    b[s[k-a]]-=1\n",
    "                    if b[s[k-a]]==c:\n",
    "                        tmp+=1 \n",
    "                    if b[s[k-a]]==(c-1):\n",
    "                        tmp-=1 \n",
    "                    if tmp==j:\n",
    "                        ans += 1 \n",
    "        return ans \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 滚动哈希+暴力\n",
    "    def equalCountSubstrings(self, s: str, count: int) -> int:\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "        \n",
    "        # 检查是否符合条件\n",
    "        def check(dp):\n",
    "            return all(num==count or num==0 for num in dp)\n",
    "\n",
    "        # 检查unique的字符个数\n",
    "        for k in range(1, 27):\n",
    "            length = count*k\n",
    "            if length > n:\n",
    "                break\n",
    "\n",
    "            # 初始化\n",
    "            dp = [0]*26\n",
    "            for i in range(length):\n",
    "                dp[ord(s[i])-ord('a')] += 1\n",
    "            ans += check(dp)\n",
    "\n",
    "            # 滚动\n",
    "            for i in range(length, n):\n",
    "                dp[ord(s[i])-ord('a')] += 1\n",
    "                dp[ord(s[i-length])-ord('a')] -= 1\n",
    "                ans += check(dp)\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalCountSubstrings(self, s: str, count: int) -> int:\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "        \n",
    "        # 检查是否符合条件\n",
    "        def check(dp):\n",
    "            return all(num==count or num==0 for num in dp)\n",
    "\n",
    "        # 检查unique的字符个数\n",
    "        for k in range(1, 27):\n",
    "            length = count*k\n",
    "            if length > n:\n",
    "                break\n",
    "\n",
    "            # 初始化\n",
    "            dp = [0]*26\n",
    "            for i in range(length):\n",
    "                dp[ord(s[i])-ord('a')] += 1\n",
    "            ans += check(dp)\n",
    "\n",
    "            # 滚动\n",
    "            for i in range(length, n):\n",
    "                dp[ord(s[i])-ord('a')] += 1\n",
    "                dp[ord(s[i-length])-ord('a')] -= 1\n",
    "                ans += check(dp)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalCountSubstrings(self, s: str, c: int) -> int:  \n",
    "        ans = 0 \n",
    "        for j in range(1, 27):\n",
    "            a  = j*c \n",
    "            if len(s)<a:\n",
    "                pass \n",
    "            else:\n",
    "                b = defaultdict(int)\n",
    "                tmp = 0\n",
    "                for k in range(a):\n",
    "                    b[s[k]]+=1\n",
    "                    if b[s[k]]==c:\n",
    "                        tmp+=1 \n",
    "                    if b[s[k]]==(c+1):\n",
    "                        tmp-=1\n",
    "                if tmp==j:\n",
    "                    ans += 1 \n",
    "                for k in range(a, len(s)):\n",
    "                    b[s[k]]+=1\n",
    "                    if b[s[k]]==c:\n",
    "                        tmp+=1 \n",
    "                    if b[s[k]]==(c+1):\n",
    "                        tmp-=1 \n",
    "                    b[s[k-a]]-=1\n",
    "                    if b[s[k-a]]==c:\n",
    "                        tmp+=1 \n",
    "                    if b[s[k-a]]==(c-1):\n",
    "                        tmp-=1 \n",
    "                    if tmp==j:\n",
    "                        ans += 1 \n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalCountSubstrings(self, s: str, count: int) -> int:\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "        \n",
    "        # 检查是否符合条件\n",
    "        def check(dp):\n",
    "            return all(num==count or num==0 for num in dp)\n",
    "\n",
    "        # 检查unique的字符个数\n",
    "        for k in range(1, 27):\n",
    "            length = count*k\n",
    "            if length > n:\n",
    "                break\n",
    "\n",
    "            # 初始化\n",
    "            dp = [0]*26\n",
    "            for i in range(length):\n",
    "                dp[ord(s[i])-ord('a')] += 1\n",
    "            ans += check(dp)\n",
    "\n",
    "            # 滚动\n",
    "            for i in range(length, n):\n",
    "                dp[ord(s[i])-ord('a')] += 1\n",
    "                dp[ord(s[i-length])-ord('a')] -= 1\n",
    "                ans += check(dp)\n",
    "        return ans\n",
    "\n",
    "# 作者：ZYS\n",
    "# 链接：https://leetcode.cn/problems/number-of-equal-count-substrings/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalCountSubstrings(self, s: str, count: int) -> int:\n",
    "        ans = 0\n",
    "        n = len(s)\n",
    "\n",
    "        for k in range(1,27):\n",
    "            length = k*count \n",
    "            if length > n:\n",
    "                break \n",
    "            \n",
    "            counter = Counter(s[:length])\n",
    "            num = sum(cnt == count for cnt in counter.values())\n",
    "            if num == k:\n",
    "                ans += 1\n",
    "\n",
    "            for i in range(length, n):\n",
    "                counter[s[i]] += 1\n",
    "                if counter[s[i]] == count:\n",
    "                    num += 1\n",
    "                elif counter[s[i]] == count + 1:\n",
    "                    num -= 1\n",
    "\n",
    "                counter[s[i-length]] -= 1\n",
    "                if counter[s[i-length]] == count:\n",
    "                    num += 1\n",
    "                elif counter[s[i-length]] == count - 1:\n",
    "                    num -= 1\n",
    "\n",
    "                if num == k:\n",
    "                    ans += 1\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalCountSubstrings(self, s: str, count: int) -> int:\n",
    "        ans=0\n",
    "        n=len(s)\n",
    "        if n<count:\n",
    "            return ans\n",
    "        temp=count\n",
    "        ss=set()\n",
    "        ss.add(count)\n",
    "        ss.add(0)\n",
    "        while temp<=26*count and temp<=n:\n",
    "            cnt=Counter(s[:temp])\n",
    "            if all( k in ss for k in cnt.values()):\n",
    "                ans+=1\n",
    "            for i in range(temp,n):\n",
    "                cnt[s[i]]+=1\n",
    "                cnt[s[i-temp]]-=1\n",
    "                if all( k in ss for k in cnt.values()):\n",
    "                    ans+=1\n",
    "            temp+=count\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalCountSubstrings(self, s: str, count: int) -> int:\n",
    "        ans = 0\n",
    "        n = len(s)\n",
    "\n",
    "        for k in range(1,27):\n",
    "            length = k*count \n",
    "            if length > n:\n",
    "                break \n",
    "            \n",
    "            counter = defaultdict(int)\n",
    "            num = 0\n",
    "            for c in s[:length]:\n",
    "                counter[c] += 1\n",
    "                if counter[c] == count:\n",
    "                    num += 1\n",
    "                elif counter[c] == count + 1:\n",
    "                    num -= 1\n",
    "            if num == k:\n",
    "                ans += 1\n",
    "\n",
    "            for i in range(length, n):\n",
    "                counter[s[i]] += 1\n",
    "                if counter[s[i]] == count:\n",
    "                    num += 1\n",
    "                elif counter[s[i]] == count + 1:\n",
    "                    num -= 1\n",
    "\n",
    "                counter[s[i-length]] -= 1\n",
    "                if counter[s[i-length]] == count:\n",
    "                    num += 1\n",
    "                elif counter[s[i-length]] == count - 1:\n",
    "                    num -= 1\n",
    "\n",
    "                if num == k:\n",
    "                    ans += 1\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalCountSubstrings(self, s: str, count: int) -> int:\n",
    "        n = len(s)\n",
    "        def helper(k: int) -> int:\n",
    "            if k > n:\n",
    "                return 0\n",
    "            cnt = Counter(s[:k])\n",
    "            ans = int(all(v == count for v in cnt.values()))\n",
    "            for i in range(k, n):\n",
    "                x, y = s[i], s[i-k]\n",
    "                cnt[x] += 1\n",
    "                cnt[y] -= 1\n",
    "                if cnt[y] == 0:\n",
    "                    del cnt[y]\n",
    "                if all(v == count for v in cnt.values()):\n",
    "                    ans += 1\n",
    "            return ans\n",
    "\n",
    "        return sum(helper(k * count) for k in range(1, 27))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalCountSubstrings(self, s: str, count: int) -> int:\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "        acc = [[0] * 26 for _ in range(n + 1)]\n",
    "\n",
    "        def check(start, end):\n",
    "            for i in range(26):\n",
    "                if (tmp := (acc[end + 1][i] - acc[start][i])) and tmp != count:\n",
    "                    return False \n",
    "            return True\n",
    "\n",
    "        for i, j in enumerate(s, 1):\n",
    "            for k in range(26):\n",
    "                acc[i][k] = acc[i - 1][k]\n",
    "            acc[i][ord(j) - ord('a')] += 1\n",
    "        for i in range(1, 27):\n",
    "            ln = i * count\n",
    "            for start in range(n):\n",
    "                if start + ln > n:\n",
    "                    break\n",
    "                end = start + ln - 1\n",
    "                if check(start, end):\n",
    "                    ans += 1\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalCountSubstrings(self, s: str, count: int) -> int:\n",
    "        cnt = [0] * 26\n",
    "        cnts = [cnt]\n",
    "        aord = ord(\"a\")\n",
    "        ans = 0\n",
    "\n",
    "        for i, c in enumerate(s):\n",
    "            cnts.append(cnts[-1][:])\n",
    "            cnts[-1][ord(c)-aord] += 1\n",
    "\n",
    "            for k in range(1,27):\n",
    "                if i - k*count < -1:\n",
    "                    break\n",
    "                if all((sm:=cnts[-1][idx] - cnts[i - k*count+1][idx]) == 0 or sm==count for idx in range(26)):\n",
    "                    ans += 1\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalCountSubstrings(self, s: str, count: int) -> int:\n",
    "        cnt = [0] * 26\n",
    "        cnts = [cnt]\n",
    "        aord = ord(\"a\")\n",
    "        ans = 0\n",
    "\n",
    "        for i, c in enumerate(s):\n",
    "            cnts.append(cnts[-1][:])\n",
    "            cnts[-1][ord(c)-aord] += 1\n",
    "\n",
    "            for k in range(1,27):\n",
    "                if i - k*count < -1:\n",
    "                    break\n",
    "                if all((sm:=cnts[-1][idx] - cnts[i - k*count+1][idx]) == 0 or sm==count for idx in range(26)):\n",
    "                    ans += 1\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalCountSubstrings(self, s: str, count: int) -> int:\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "        acc = [[0] * 26 for _ in range(n + 1)]\n",
    "\n",
    "        def check(start, end):\n",
    "            for i in range(26):\n",
    "                if (tmp := (acc[end + 1][i] - acc[start][i])) and tmp != count:\n",
    "                    return False \n",
    "            return True\n",
    "\n",
    "        for i, j in enumerate(s, 1):\n",
    "            for k in range(26):\n",
    "                acc[i][k] = acc[i - 1][k]\n",
    "            acc[i][ord(j) - ord('a')] += 1\n",
    "        for i in range(1, 27):\n",
    "            ln = i * count\n",
    "            if ln > n:\n",
    "                break\n",
    "            for start in range(n):\n",
    "                if start + ln > n:\n",
    "                    break\n",
    "                end = start + ln - 1\n",
    "                if check(start, end):\n",
    "                    ans += 1\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equalCountSubstrings(self, s: str, count: int) -> int:\n",
    "        cnt = [0] * 26\n",
    "        cnts = [cnt]\n",
    "        aord = ord(\"a\")\n",
    "        ans = 0\n",
    "\n",
    "        for i, c in enumerate(s):\n",
    "            cnts.append(cnts[-1][:])\n",
    "            cnts[-1][ord(c)-aord] += 1\n",
    "\n",
    "            for k in range(1,27):\n",
    "                if i - k*count < -1:\n",
    "                    break\n",
    "                if all((sm:=cnts[-1][idx] - cnts[i - k*count+1][idx]) == 0 or sm==count for idx in range(26)):\n",
    "                    ans += 1\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import *\n",
    "from heapq import *\n",
    "from sys import *\n",
    "from math import *\n",
    "from itertools import *\n",
    "from functools import *\n",
    "from string import *\n",
    "from bisect import *\n",
    "from graphlib import *\n",
    "from sortedcontainers import *\n",
    "from copy import *\n",
    "\n",
    "class Solution:\n",
    "    def equalCountSubstrings(self, s: str, count: int) -> int:\n",
    "        cnts = [0] * 26\n",
    "        acc = [deepcopy(cnts)]\n",
    "        s = [ord(x)-ord(\"a\") for x in s]\n",
    "        for x in s:\n",
    "            cnts[x] += 1\n",
    "            acc.append(deepcopy(cnts))\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "        for i, x in enumerate(s):\n",
    "            for d in range(1, 27):\n",
    "                j = d * count + i\n",
    "                if j <= n:\n",
    "                    t = 0\n",
    "                    for c in range(26):\n",
    "                        if acc[j][c] - acc[i][c] not in (0, count): break\n",
    "                        if count == acc[j][c] - acc[i][c]: t += 1\n",
    "                    if t == d: ans += 1\n",
    "        return ans\n",
    "\n",
    "        \n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
